package com.my.sort;

/**
 * Created by ZhongGang
 * at 2018/10/9 15:38
 * <p>
 * 双基准排序
 * 选取两个位置的元素作为基准元素，称为左基准元素和右基准元素，需要保证左基准元素小于右基准元素
 * 通过选取排序数组的第一个元素和最后一个元素作为基准元素
 * 较之单基准排序只考虑了CPU的效率，双基准元素通过减少元素的扫描次数提升内存使用效率，虽然比较次数更多，但仍然了提高排序效率
 */
public class DualPivotQuickSorter<T extends Comparable<T>> implements Sortable<T> {

    @Override
    public T[] sort(T[] elements) {
        if (elements == null || elements.length < 2) {
            return elements;
        }

        dualPivotQuickSort(elements, 0, elements.length - 1);

        return elements;
    }

    private void dualPivotQuickSort(T[] elements, int left, int right) {
        if (left >= right) {
            return;
        }

        //如果左基准元素大于右基准元素，交换两者的元素
        if (elements[left].compareTo(elements[right]) > 0) {
            T tmp = elements[left];
            elements[left] = elements[right];
            elements[right] = tmp;
        }

        T p = elements[left];
        T q = elements[right];
        int e = left + 1;
        int g = right - 1;
        int k = e;

        while (k <= g) {
            if (elements[k].compareTo(p) < 0) {
                T tmp = elements[k];
                elements[k] = elements[e];
                elements[e] = tmp;
                e += 1;
            } else if (elements[k].compareTo(q) > -1) {
                while (elements[g].compareTo(q) > 0 && k < g) {
                    g -= 1;
                }
                T tmp = elements[k];
                elements[k] = elements[g];
                elements[g] = tmp;
                g -= 1;
                if (elements[k].compareTo(p) < 0) {
                    T t = elements[k];
                    elements[k] = elements[e];
                    elements[e] = t;
                    e += 1;
                }
            }
            k += 1;
        }

        e -= 1;
        g += 1;
        elements[left] = elements[e];
        elements[e] = p;
        elements[right] = elements[g];
        elements[g] = q;

        dualPivotQuickSort(elements, left, e - 1);
        dualPivotQuickSort(elements, e + 1, g - 1);
        dualPivotQuickSort(elements, g + 1, right);
    }
}
